Advances in our understanding of T cell activation at a molecular level have permitted the manipulation of T cell regulation in cancer patients. A newly discovered molecule involved in T cell regulation is PD-1, which like CTLA-4 is upregulated on activated CD4 and CD8 T cells but functions through Akt pathways to alter T cell receptor signaling in T cells. A human antibody directed against PD-1 which abrogates its function has been shown in animal tumor models to have potent anti-tumor activity alone and in combination with vaccines. In vitro experiments with melanoma patient peripheral blood mononuclear cell indicated that antibody mediated PD-1 abrogation increased the generation of antigen specific T cells that were lytic, functional, gamma-interferon secreting effector cells. PD-1 antibody increased the proportion of cells that expressed CD107a, augmented avidity and caused an increase in proliferating CD8 cells after antigen exposure, promoting cell survival. PD-1 antibody could also overcome the inhibition of T cell proliferation that occurred in the presence of natural T regulatory cells. When PD-1 blockade was combined with CTLA-4 blockade in vivo in animal models there was an additive or even synergistic anti-tumor effect. When both molecules were abrogated in vitro with human melanoma specific T cells, generation of antigen specific functional T cells was markedly increased. Based on those extensive data, the investigators propose to perform a Phase 1 trial of escalating doses of anti-PD-1 antibody with a multi-peptide vaccine in cohorts of 10 melanoma patients each with endpoints of toxicity, definition of a MTD and comparison of immune and other surrogate assays between cohorts. After a dose of PD-1 antibody given repetitively with a vaccine that optimally stimulates immunity and is well tolerated is defined, the investigators will perform a Phase 2 study of the combination of PD-1 and CTLA-4 abrogating antibodies with a multi-peptide vaccine in patients with chemotherapy resistant metastatic melanoma.